package com.wenx.sort;

import java.util.Arrays;
import java.util.stream.Stream;

public class QuickSort {

    public static void main(String[] args) {

        int[] array = Stream.of(7, 1, 3, 5, 13, 9, 8, 6, 11)
                .mapToInt(Integer::byteValue)
                .toArray();

        quickSort(array);

        Arrays.stream(array).forEach(i -> {
            System.out.print(i + " ");
        });
    }

    private static void quickSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) {
            return;
        }
        sort(array, 0, array.length - 1);
    }

    private static void sort(int[] array, int left, int right) {
        //边界值判断
        if (left > right) {
            return;
        }
        int base = array[left];
        int i = left, j = right;
        while (i != j) {

            //先从右边找比基数小的
            while (array[j] >= base && i < j) {
                j--;
            }

            //再从左边找比基数大的数
            while (array[i] <= base && i < j) {
                i++;
            }

            //交换
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        //将基准值放到遍历的中间位置
        array[left] = array[i];
        array[i] = base;

        //递归
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }

}
